/*
题目: 划分为K个相等的子集
给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
 */
public class CanPartitionKSubsets {
    int n = 0;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        //以桶为单位进行回溯
        n = k;
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (sum % k != 0) {
            return false;
        }

        sum /= k;
        int[] bucket = new int[k];
        Arrays.sort(nums); //排序
        Arrays.fill(bucket, sum);

        //排序后从后开始遍历, 提高回溯效率
        return backTrack(nums, bucket, nums.length - 1);
    }

    private boolean backTrack(int[] nums, int[] bucket, int index) {
        if (index < 0) {
            return true;
        }

        for (int i = 0; i < n; i++) {  //遍历每一个桶
            //如果这个if条件为true, 说明这个桶会和上一个桶做同样的选择, 而上一个桶的选择是错误的
            if(i > 0 && bucket[i] == bucket[i-1]) continue;  //直接减少2200ms

            if (bucket[i] - nums[index] >= nums[0] || bucket[i] == nums[index]) {
                bucket[i] -= nums[index];
                if (backTrack(nums, bucket, index - 1)) {
                    return true;
                }
                bucket[i] += nums[index];  //回溯
            }
        }
        return false;
    }
}
